package other;

import java.util.Arrays;

public class 数组排序 {

    /***
     * 归并排序借助的额外内存
     */
    private static int[] aux;
/**
 * 本次排序作为学习数组排序的总结
 * 从描述
 * 1、排序的特性：稳定性
 * 2、时间复杂度
 * 3、空间复杂度
 * 4、是否为比较排序：
 *      快排、归并、堆排、冒泡等都属于比较排序
 * 5、等维度进行分析
 */

    /**
     * @author Beau
     * @param args
     */
    public static void main(String[] args) {
        int[] nums={4,1,6,3,2,7};
//        //1.归并排序
//        aux=new int[nums.length];
//        mergeSort(nums,0,nums.length-1);
//
//        //2、快排
//        quickSort(nums,0,nums.length-1);
//
//        //3、插入排序
//        insertSort(nums);
//
//        //4、冒泡排序
//        bubbleSort(nums);
//
//        //5、选择排序
//        selectSort(nums);

        //6、堆排序
        heapSort(nums);


        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }

    /**
     * 堆排序
     * @param nums
     */
    private static void heapSort(int[] nums) {
        //构造堆
        int[] heap=new int[nums.length+1];
        heap[0]=0;
        for (int i = 0; i < nums.length; i++) {
            heap[i+1]=nums[i];
        }

        int N=nums.length;
        //构造堆
        for (int i = N/2; i >=1 ; i--) {
            sink(heap,i,N);
        }
        while(N>1){
            //交换第一个和最后一个的值
            heap[1]=heap[1]^heap[N];
            heap[N]=heap[1]^heap[N];
            heap[1]=heap[1]^heap[N];
            sink(heap,1,--N);
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i]=heap[i+1];
        }


    }

    private static void sink(int[] heap,int k,int N){
        while(k*2<=N){
            int s=2*k;
            if(s+1<=N&&heap[s]<heap[s+1]){
                s=s+1;
            }
            //交换
            if(heap[k]<heap[s]){
                heap[k]=heap[k]^heap[s];
                heap[s]=heap[k]^heap[s];
                heap[k]=heap[k]^heap[s];
            }
            k=s;
        }

    }

    /**
     * 稳定性：最稳定的排序算法
     * 时间复杂度：无论什么情况下都是 O（n^2)
     * 选择排序 (保证左边的始终有序）
     * @param nums
     */
    private static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min=i;
            int minV=nums[i];
            for (int j = 1; j < nums.length; j++) {
                if(nums[j]<minV){
                    min=j;
                    minV=nums[j];
                }
            }
            if(min!=i){
                nums[i]=nums[i]^nums[min];
                nums[min]=nums[i]^nums[min];
                nums[i]=nums[i]^nums[min];
            }
        }
    }

    /**
     * 稳定
     * 平均情况：T(n) = O(n2)
     * 冒泡排序
     * 时间复杂度为 O（n^2)
     * @param nums
     */
    private static void bubbleSort(int[] nums) {
        for (int i = nums.length-1; i >=1; i--) {
            boolean is_Con=false;
            for (int j = 1; j <= i; j++) {
                if(nums[j]<nums[j-1]){
                    nums[j]=nums[j]^nums[j-1];
                    nums[j-1]=nums[j]^nums[j-1];
                    nums[j]=nums[j]^nums[j-1];
                    is_Con=true;
                }
            }
            if(!is_Con){
                break;
            }

        }
    }

    /**
     * 稳定的排序
     * O（n^2)
     * 插入排序
     * @param nums
     */
    private static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int val=nums[i];
            for (int j = 0; j < i; j++) {
                if(nums[j]>val){
                    for (int k = i; k >= j+1; k--) {
                        nums[k]=nums[k-1];
                    }
                    nums[j]=val;
                    break;
                }
            }


        }

    }


    /**
     * 快排
     * 不稳定的排序
     * 最佳情况：T(n) = O(nlogn)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(nlogn)
     * 1、找分割点
     * 2、对分割点 左右俩个区间进行相同的操作
     * @param nums
     * @param l
     * @param r
     */
    private static void quickSort(int[] nums, int l, int r) {
        if(l>=r) {
            return;
        }
        //找l-r区间的位置 p
        int p=partition(nums,l,r);
        quickSort(nums,l,p-1);
        quickSort(nums,p+1,r);
    }

    /**
     * 找分割点
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] nums, int l, int r) {
        int val=nums[l];
        int i=l+1;
        int j=r;
        while(i<=j){
            while(i<=j&&nums[i]<val){
                i++;
            }
            while (i<=j&&nums[j]>=val){
                j--;
            }
            if(i<=j){
                nums[i]=nums[i]^nums[j];
                nums[j]=nums[i]^nums[j];
                nums[i]=nums[i]^nums[j];
            }
        }
        if(i!=l+1){
            nums[i-1]=nums[i-1]^nums[l];
            nums[l]=nums[i-1]^nums[l];
            nums[i-1]=nums[i-1]^nums[l];
        }
        return i-1;

    }


    /***
     * 归并排序
     * 稳定的排序
     * 归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
     * @param nums
     * @param l
     * @param r
     */
    private static void mergeSort(int[] nums, int l, int r) {
        if(l>=r) {
            return;
        }

        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);

    }

    /**
     * 合并
     * @param nums
     * @param l
     * @param r
     */
    private static void merge(int[] nums, int l,int mid,int r) {
        for (int i = l; i < r+1; i++) {
            aux[i]=nums[i];
        }
        int i=l;
        int j=mid+1;

        for (int k = l; k <r+1 ; k++) {
            if(i!=mid+1&&j!=r+1){
                if(aux[i]<=aux[j]){
                    nums[k]=aux[i++];
                }else{
                    nums[k]=aux[j++];
                }
            }else if(i==mid+1){
                nums[k]=aux[j++];
            }else{
                nums[k]=aux[i++];
            }

        }

    }


}
